//package deque;
/*
 * Description: 实现双向链表，
 * 1.增加删除的时间复杂度为O(1)
 * 2.get方法使用遍历，时间复杂度为O(N)
 * 3.size函数时间复杂度为O(1)
 * 4.不维护已经不在链表中的对象的引用，避免内存泄漏
 * Author: AMark
 * Date:1/23/2024
 * Time:2:16 PM
 */

import java.util.Iterator;

public class LinkedListDeque<T> {
    private class Node {
        //赋初始值为null
        public T item= null;
        public Node next;
        public Node prev;

        public Node(T x) {
            item = x;
            next = null;
            prev = null;
        }
    }
    //哨兵，注意，由于没有头节点和尾节点，所以哨兵的next和prev指向自己,同时注意要将其赋初始值为null
    private Node sentinel = new Node(null);
    private int size;
    //头插法
    public void addFirst(T x) {
        Node newNode = new Node(x);
        if (isEmpty()) {
            sentinel.next = newNode;
            newNode.prev = sentinel;
            newNode.next = sentinel;
            sentinel.prev = newNode;
        } else {
            newNode.next = sentinel.next;
            newNode.prev = sentinel;
            sentinel.next.prev = newNode;
            sentinel.next = newNode;
        }
        size += 1;
    }
    //尾插法
    public void addLast(T x) {
        Node newNode = new Node(x);
        if (isEmpty()) {
            sentinel.next = newNode;
            newNode.prev = sentinel;
            newNode.next = sentinel;
            sentinel.prev = newNode;
        } else {
            newNode.next = sentinel;
            newNode.prev = sentinel.prev;
            sentinel.prev.next = newNode;
            sentinel.prev = newNode;
        }
        size += 1;
    }
    //判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    //获得大小

    //打印链表,使用foreach
    public void printDeque() {
        Node p = sentinel.next;
        while (p != sentinel) {
            System.out.print(p.item + " ");
            p = p.next;
        }
        System.out.println();
    }
    public T removeFirst() {
        if (isEmpty()) {
            return null;
        }
        Node p = sentinel.next;
        sentinel.next = p.next;
        p.next.prev = sentinel;
        size -= 1;
        return p.item;
    }
    public T removeLast() {
        if (isEmpty()) {
            return null;
        }
        Node p = sentinel.prev;
        sentinel.prev = p.prev;
        p.prev.next = sentinel;
        size -= 1;
        return p.item;
    }
    public T get(int index) {
        if (index >= size) {
            return null;
        }
        Node p = sentinel.next;
        while (index > 0) {
            p = p.next;
            index -= 1;
        }
        return p.item;
    }

    public Iterator<T> iterator() {
        return new LinkedListDequeIterator();
    }
    private class LinkedListDequeIterator implements Iterator<T> {
        private Node p;
        public LinkedListDequeIterator() {
            p = sentinel.next;
        }
        public boolean hasNext() {
            return p != sentinel;
        }
        public T next() {
            T item = p.item;
            p = p.next;
            return item;
        }
    }
    //判断两个链表是否相等，包括大小和元素
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (o.getClass() != LinkedListDeque.class) {
            return false;
        }
        LinkedListDeque<T> other = (LinkedListDeque<T>) o;
        if (other.size() != size) {
            return false;
        }
        Node p = sentinel.next;
        Node q = other.sentinel.next;
        while (p != sentinel) {
            if (!p.item.equals(q.item)) {
                return false;
            }
            p = p.next;
            q = q.next;
        }
        return true;
    }
}
